// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/loop-analysis.h"

#include "src/compiler/graph.h"
#include "src/compiler/node-marker.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"
#include "src/zone/zone.h"

namespace v8 {
namespace internal {
    namespace compiler {

#define OFFSET(x) ((x)&0x1F)
#define BIT(x) (1u << OFFSET(x))
#define INDEX(x) ((x) >> 5)

        // Temporary information for each node during marking.
        struct NodeInfo {
            Node* node;
            NodeInfo* next; // link in chaining loop members
        };

        // Temporary loop info needed during traversal and building the loop tree.
        struct TempLoopInfo {
            Node* header;
            NodeInfo* header_list;
            NodeInfo* exit_list;
            NodeInfo* body_list;
            LoopTree::Loop* loop;
        };

        // Encapsulation of the loop finding algorithm.
        // -----------------------------------------------------------------------------
        // Conceptually, the contents of a loop are those nodes that are "between" the
        // loop header and the backedges of the loop. Graphs in the soup of nodes can
        // form improper cycles, so standard loop finding algorithms that work on CFGs
        // aren't sufficient. However, in valid TurboFan graphs, all cycles involve
        // either a {Loop} node or a phi. The {Loop} node itself and its accompanying
        // phis are treated together as a set referred to here as the loop header.
        // This loop finding algorithm works by traversing the graph in two directions,
        // first from nodes to their inputs, starting at {end}, then in the reverse
        // direction, from nodes to their uses, starting at loop headers.
        // 1 bit per loop per node per direction are required during the marking phase.
        // To handle nested loops correctly, the algorithm must filter some reachability
        // marks on edges into/out-of the loop header nodes.
        class LoopFinderImpl {
        public:
            LoopFinderImpl(Graph* graph, LoopTree* loop_tree, Zone* zone)
                : zone_(zone)
                , end_(graph->end())
                , queue_(zone)
                , queued_(graph, 2)
                , info_(graph->NodeCount(), { nullptr, nullptr }, zone)
                , loops_(zone)
                , loop_num_(graph->NodeCount(), -1, zone)
                , loop_tree_(loop_tree)
                , loops_found_(0)
                , width_(0)
                , backward_(nullptr)
                , forward_(nullptr)
            {
            }

            void Run()
            {
                PropagateBackward();
                PropagateForward();
                FinishLoopTree();
            }

            void Print()
            {
                // Print out the results.
                for (NodeInfo& ni : info_) {
                    if (ni.node == nullptr)
                        continue;
                    for (int i = 1; i <= loops_found_; i++) {
                        int index = ni.node->id() * width_ + INDEX(i);
                        bool marked_forward = forward_[index] & BIT(i);
                        bool marked_backward = backward_[index] & BIT(i);
                        if (marked_forward && marked_backward) {
                            PrintF("X");
                        } else if (marked_forward) {
                            PrintF(">");
                        } else if (marked_backward) {
                            PrintF("<");
                        } else {
                            PrintF(" ");
                        }
                    }
                    PrintF(" #%d:%s\n", ni.node->id(), ni.node->op()->mnemonic());
                }

                int i = 0;
                for (TempLoopInfo& li : loops_) {
                    PrintF("Loop %d headed at #%d\n", i, li.header->id());
                    i++;
                }

                for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
                    PrintLoop(loop);
                }
            }

        private:
            Zone* zone_;
            Node* end_;
            NodeDeque queue_;
            NodeMarker<bool> queued_;
            ZoneVector<NodeInfo> info_;
            ZoneVector<TempLoopInfo> loops_;
            ZoneVector<int> loop_num_;
            LoopTree* loop_tree_;
            int loops_found_;
            int width_;
            uint32_t* backward_;
            uint32_t* forward_;

            int num_nodes()
            {
                return static_cast<int>(loop_tree_->node_to_loop_num_.size());
            }

            // Tb = Tb | (Fb - loop_filter)
            bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter)
            {
                if (from == to)
                    return false;
                uint32_t* fp = &backward_[from->id() * width_];
                uint32_t* tp = &backward_[to->id() * width_];
                bool change = false;
                for (int i = 0; i < width_; i++) {
                    uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF;
                    uint32_t prev = tp[i];
                    uint32_t next = prev | (fp[i] & mask);
                    tp[i] = next;
                    if (!change && (prev != next))
                        change = true;
                }
                return change;
            }

            // Tb = Tb | B
            bool SetBackwardMark(Node* to, int loop_num)
            {
                uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)];
                uint32_t prev = tp[0];
                uint32_t next = prev | BIT(loop_num);
                tp[0] = next;
                return next != prev;
            }

            // Tf = Tf | B
            bool SetForwardMark(Node* to, int loop_num)
            {
                uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)];
                uint32_t prev = tp[0];
                uint32_t next = prev | BIT(loop_num);
                tp[0] = next;
                return next != prev;
            }

            // Tf = Tf | (Ff & Tb)
            bool PropagateForwardMarks(Node* from, Node* to)
            {
                if (from == to)
                    return false;
                bool change = false;
                int findex = from->id() * width_;
                int tindex = to->id() * width_;
                for (int i = 0; i < width_; i++) {
                    uint32_t marks = backward_[tindex + i] & forward_[findex + i];
                    uint32_t prev = forward_[tindex + i];
                    uint32_t next = prev | marks;
                    forward_[tindex + i] = next;
                    if (!change && (prev != next))
                        change = true;
                }
                return change;
            }

            bool IsInLoop(Node* node, int loop_num)
            {
                int offset = node->id() * width_ + INDEX(loop_num);
                return backward_[offset] & forward_[offset] & BIT(loop_num);
            }

            // Propagate marks backward from loop headers.
            void PropagateBackward()
            {
                ResizeBackwardMarks();
                SetBackwardMark(end_, 0);
                Queue(end_);

                while (!queue_.empty()) {
                    Node* node = queue_.front();
                    info(node);
                    queue_.pop_front();
                    queued_.Set(node, false);

                    int loop_num = -1;
                    // Setup loop headers first.
                    if (node->opcode() == IrOpcode::kLoop) {
                        // found the loop node first.
                        loop_num = CreateLoopInfo(node);
                    } else if (NodeProperties::IsPhi(node)) {
                        // found a phi first.
                        Node* merge = node->InputAt(node->InputCount() - 1);
                        if (merge->opcode() == IrOpcode::kLoop) {
                            loop_num = CreateLoopInfo(merge);
                        }
                    } else if (node->opcode() == IrOpcode::kLoopExit) {
                        // Intentionally ignore return value. Loop exit node marks
                        // are propagated normally.
                        CreateLoopInfo(node->InputAt(1));
                    } else if (node->opcode() == IrOpcode::kLoopExitValue || node->opcode() == IrOpcode::kLoopExitEffect) {
                        Node* loop_exit = NodeProperties::GetControlInput(node);
                        // Intentionally ignore return value. Loop exit node marks
                        // are propagated normally.
                        CreateLoopInfo(loop_exit->InputAt(1));
                    }

                    // Propagate marks backwards from this node.
                    for (int i = 0; i < node->InputCount(); i++) {
                        Node* input = node->InputAt(i);
                        if (IsBackedge(node, i)) {
                            // Only propagate the loop mark on backedges.
                            if (SetBackwardMark(input, loop_num))
                                Queue(input);
                        } else {
                            // Entry or normal edge. Propagate all marks except loop_num.
                            if (PropagateBackwardMarks(node, input, loop_num))
                                Queue(input);
                        }
                    }
                }
            }

            // Make a new loop if necessary for the given node.
            int CreateLoopInfo(Node* node)
            {
                DCHECK_EQ(IrOpcode::kLoop, node->opcode());
                int loop_num = LoopNum(node);
                if (loop_num > 0)
                    return loop_num;

                loop_num = ++loops_found_;
                if (INDEX(loop_num) >= width_)
                    ResizeBackwardMarks();

                // Create a new loop.
                loops_.push_back({ node, nullptr, nullptr, nullptr, nullptr });
                loop_tree_->NewLoop();
                SetLoopMarkForLoopHeader(node, loop_num);
                return loop_num;
            }

            void SetLoopMark(Node* node, int loop_num)
            {
                info(node); // create the NodeInfo
                SetBackwardMark(node, loop_num);
                loop_tree_->node_to_loop_num_[node->id()] = loop_num;
            }

            void SetLoopMarkForLoopHeader(Node* node, int loop_num)
            {
                DCHECK_EQ(IrOpcode::kLoop, node->opcode());
                SetLoopMark(node, loop_num);
                for (Node* use : node->uses()) {
                    if (NodeProperties::IsPhi(use)) {
                        SetLoopMark(use, loop_num);
                    }

                    // Do not keep the loop alive if it does not have any backedges.
                    if (node->InputCount() <= 1)
                        continue;

                    if (use->opcode() == IrOpcode::kLoopExit) {
                        SetLoopMark(use, loop_num);
                        for (Node* exit_use : use->uses()) {
                            if (exit_use->opcode() == IrOpcode::kLoopExitValue || exit_use->opcode() == IrOpcode::kLoopExitEffect) {
                                SetLoopMark(exit_use, loop_num);
                            }
                        }
                    }
                }
            }

            void ResizeBackwardMarks()
            {
                int new_width = width_ + 1;
                int max = num_nodes();
                uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max);
                memset(new_backward, 0, new_width * max * sizeof(uint32_t));
                if (width_ > 0) { // copy old matrix data.
                    for (int i = 0; i < max; i++) {
                        uint32_t* np = &new_backward[i * new_width];
                        uint32_t* op = &backward_[i * width_];
                        for (int j = 0; j < width_; j++)
                            np[j] = op[j];
                    }
                }
                width_ = new_width;
                backward_ = new_backward;
            }

            void ResizeForwardMarks()
            {
                int max = num_nodes();
                forward_ = zone_->NewArray<uint32_t>(width_ * max);
                memset(forward_, 0, width_ * max * sizeof(uint32_t));
            }

            // Propagate marks forward from loops.
            void PropagateForward()
            {
                ResizeForwardMarks();
                for (TempLoopInfo& li : loops_) {
                    SetForwardMark(li.header, LoopNum(li.header));
                    Queue(li.header);
                }
                // Propagate forward on paths that were backward reachable from backedges.
                while (!queue_.empty()) {
                    Node* node = queue_.front();
                    queue_.pop_front();
                    queued_.Set(node, false);
                    for (Edge edge : node->use_edges()) {
                        Node* use = edge.from();
                        if (!IsBackedge(use, edge.index())) {
                            if (PropagateForwardMarks(node, use))
                                Queue(use);
                        }
                    }
                }
            }

            bool IsLoopHeaderNode(Node* node)
            {
                return node->opcode() == IrOpcode::kLoop || NodeProperties::IsPhi(node);
            }

            bool IsLoopExitNode(Node* node)
            {
                return node->opcode() == IrOpcode::kLoopExit || node->opcode() == IrOpcode::kLoopExitValue || node->opcode() == IrOpcode::kLoopExitEffect;
            }

            bool IsBackedge(Node* use, int index)
            {
                if (LoopNum(use) <= 0)
                    return false;
                if (NodeProperties::IsPhi(use)) {
                    return index != NodeProperties::FirstControlIndex(use) && index != kAssumedLoopEntryIndex;
                } else if (use->opcode() == IrOpcode::kLoop) {
                    return index != kAssumedLoopEntryIndex;
                }
                DCHECK(IsLoopExitNode(use));
                return false;
            }

            int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; }

            NodeInfo& info(Node* node)
            {
                NodeInfo& i = info_[node->id()];
                if (i.node == nullptr)
                    i.node = node;
                return i;
            }

            void Queue(Node* node)
            {
                if (!queued_.Get(node)) {
                    queue_.push_back(node);
                    queued_.Set(node, true);
                }
            }

            void AddNodeToLoop(NodeInfo* node_info, TempLoopInfo* loop, int loop_num)
            {
                if (LoopNum(node_info->node) == loop_num) {
                    if (IsLoopHeaderNode(node_info->node)) {
                        node_info->next = loop->header_list;
                        loop->header_list = node_info;
                    } else {
                        DCHECK(IsLoopExitNode(node_info->node));
                        node_info->next = loop->exit_list;
                        loop->exit_list = node_info;
                    }
                } else {
                    node_info->next = loop->body_list;
                    loop->body_list = node_info;
                }
            }

            void FinishLoopTree()
            {
                DCHECK(loops_found_ == static_cast<int>(loops_.size()));
                DCHECK(loops_found_ == static_cast<int>(loop_tree_->all_loops_.size()));

                // Degenerate cases.
                if (loops_found_ == 0)
                    return;
                if (loops_found_ == 1)
                    return FinishSingleLoop();

                for (int i = 1; i <= loops_found_; i++)
                    ConnectLoopTree(i);

                size_t count = 0;
                // Place the node into the innermost nested loop of which it is a member.
                for (NodeInfo& ni : info_) {
                    if (ni.node == nullptr)
                        continue;

                    TempLoopInfo* innermost = nullptr;
                    int innermost_index = 0;
                    int pos = ni.node->id() * width_;
                    // Search the marks word by word.
                    for (int i = 0; i < width_; i++) {
                        uint32_t marks = backward_[pos + i] & forward_[pos + i];

                        for (int j = 0; j < 32; j++) {
                            if (marks & (1u << j)) {
                                int loop_num = i * 32 + j;
                                if (loop_num == 0)
                                    continue;
                                TempLoopInfo* loop = &loops_[loop_num - 1];
                                if (innermost == nullptr || loop->loop->depth_ > innermost->loop->depth_) {
                                    innermost = loop;
                                    innermost_index = loop_num;
                                }
                            }
                        }
                    }
                    if (innermost == nullptr)
                        continue;

                    // Return statements should never be found by forward or backward walk.
                    CHECK(ni.node->opcode() != IrOpcode::kReturn);

                    AddNodeToLoop(&ni, innermost, innermost_index);
                    count++;
                }

                // Serialize the node lists for loops into the loop tree.
                loop_tree_->loop_nodes_.reserve(count);
                for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
                    SerializeLoop(loop);
                }
            }

            // Handle the simpler case of a single loop (no checks for nesting necessary).
            void FinishSingleLoop()
            {
                // Place nodes into the loop header and body.
                TempLoopInfo* li = &loops_[0];
                li->loop = &loop_tree_->all_loops_[0];
                loop_tree_->SetParent(nullptr, li->loop);
                size_t count = 0;
                for (NodeInfo& ni : info_) {
                    if (ni.node == nullptr || !IsInLoop(ni.node, 1))
                        continue;

                    // Return statements should never be found by forward or backward walk.
                    CHECK(ni.node->opcode() != IrOpcode::kReturn);

                    AddNodeToLoop(&ni, li, 1);
                    count++;
                }

                // Serialize the node lists for the loop into the loop tree.
                loop_tree_->loop_nodes_.reserve(count);
                SerializeLoop(li->loop);
            }

            // Recursively serialize the list of header nodes and body nodes
            // so that nested loops occupy nested intervals.
            void SerializeLoop(LoopTree::Loop* loop)
            {
                int loop_num = loop_tree_->LoopNum(loop);
                TempLoopInfo& li = loops_[loop_num - 1];

                // Serialize the header.
                loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
                for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) {
                    loop_tree_->loop_nodes_.push_back(ni->node);
                    loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
                }

                // Serialize the body.
                loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
                for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) {
                    loop_tree_->loop_nodes_.push_back(ni->node);
                    loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
                }

                // Serialize nested loops.
                for (LoopTree::Loop* child : loop->children_)
                    SerializeLoop(child);

                // Serialize the exits.
                loop->exits_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
                for (NodeInfo* ni = li.exit_list; ni != nullptr; ni = ni->next) {
                    loop_tree_->loop_nodes_.push_back(ni->node);
                    loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
                }

                loop->exits_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
            }

            // Connect the LoopTree loops to their parents recursively.
            LoopTree::Loop* ConnectLoopTree(int loop_num)
            {
                TempLoopInfo& li = loops_[loop_num - 1];
                if (li.loop != nullptr)
                    return li.loop;

                NodeInfo& ni = info(li.header);
                LoopTree::Loop* parent = nullptr;
                for (int i = 1; i <= loops_found_; i++) {
                    if (i == loop_num)
                        continue;
                    if (IsInLoop(ni.node, i)) {
                        // recursively create potential parent loops first.
                        LoopTree::Loop* upper = ConnectLoopTree(i);
                        if (parent == nullptr || upper->depth_ > parent->depth_) {
                            parent = upper;
                        }
                    }
                }
                li.loop = &loop_tree_->all_loops_[loop_num - 1];
                loop_tree_->SetParent(parent, li.loop);
                return li.loop;
            }

            void PrintLoop(LoopTree::Loop* loop)
            {
                for (int i = 0; i < loop->depth_; i++)
                    PrintF("  ");
                PrintF("Loop depth = %d ", loop->depth_);
                int i = loop->header_start_;
                while (i < loop->body_start_) {
                    PrintF(" H#%d", loop_tree_->loop_nodes_[i++]->id());
                }
                while (i < loop->exits_start_) {
                    PrintF(" B#%d", loop_tree_->loop_nodes_[i++]->id());
                }
                while (i < loop->exits_end_) {
                    PrintF(" E#%d", loop_tree_->loop_nodes_[i++]->id());
                }
                PrintF("\n");
                for (LoopTree::Loop* child : loop->children_)
                    PrintLoop(child);
            }
        };

        LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone)
        {
            LoopTree* loop_tree = new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone());
            LoopFinderImpl finder(graph, loop_tree, zone);
            finder.Run();
            if (FLAG_trace_turbo_loop) {
                finder.Print();
            }
            return loop_tree;
        }

        Node* LoopTree::HeaderNode(Loop* loop)
        {
            Node* first = *HeaderNodes(loop).begin();
            if (first->opcode() == IrOpcode::kLoop)
                return first;
            DCHECK(IrOpcode::IsPhiOpcode(first->opcode()));
            Node* header = NodeProperties::GetControlInput(first);
            DCHECK_EQ(IrOpcode::kLoop, header->opcode());
            return header;
        }

    } // namespace compiler
} // namespace internal
} // namespace v8
